package demo;

import java.util.Stack;

public class TestSingList {
    static class Node {
        public int val;
        public Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Node head;//表示存储当前列表的头结点的引用。

    public void creatList() {
        Node node = new Node(12);
        Node node2 = new Node(12);
        Node node3 = new Node(12);
        Node node4 = new Node(14);
        Node node5 = new Node(15);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = null;
        head = node;

    }

    public void display() {
        Node cur = this.head;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }

    }

    public void addFirst(int data) {

        Node nodefirst=new Node(data);
        nodefirst.next=head;
        head=nodefirst;

    }


    public void addLast(int data) {
        Node nodeLast=new Node(data);
        if (head==null){
            head=nodeLast;
        }else {
            Node cur = head;
            while(cur.next!=null){
                cur=cur.next;
            }
            cur.next=nodeLast;
        }

    }
    private void checkIndex(int index)  {
        if(index<0||index>size())
            throw new IndexNotLegalException("index位置不合法");
    }

    public void addIndex(int index, int data){
        if (index==0) {
            addFirst(data);
            return;
        }
        if (index==size()){
            addLast(data);
            return;
        }
        if(index<0||index>size()){
            checkIndex(index);
            return;
        }
        Node node = new Node(data);
        Node cur = findIndexSubOfOne(index);
        node.next=cur.next;
        cur.next=node;

    }
    private Node findIndexSubOfOne(int index){
        Node cur=head;
        while (index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
    }


    public boolean contains(int key) {
        Node cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur=cur.next;
        }
        return false;
    }


    public void remove(int key) {
        if (head.val==key){
            head=head.next;
            return;
        }
        Node cur=searchPrevOfKey(key);
        Node node = cur.next;
        cur.next=node.next;


    }
    private Node searchPrevOfKey(int key){
        Node cur=head;
        while (cur.next!=null){
            if (cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
    }


    public void removeAllKey(int key) {
        searchPrevOfKey3(key);

    }
    /*   private void searchPrevOfKey2(int key){
           Node cur=head;
           while (cur.next!=null){
               if (cur.next.val==key){
                   cur.next=cur.next.next;
                   continue;
               }
               cur=cur.next;
           }
           if (head.val==key){
               head=head.next;
               return;
           }
       }*/
    private void searchPrevOfKey3(int key){
        Node pre=head;
        Node cur=head.next;

        while(cur!=null){
            if (cur.val==key){
                pre.next=cur.next;
                cur=cur.next;

            }else {
                pre=pre.next;
                cur=cur.next;
            }
            if (head.val==key){
                head=head.next;
            }
        }

    }


    public int size() {
        Node cur = head;
        int count=0;
        while (cur != null) {
            count++;
            cur=cur.next;
        }
        return count;
    }


    public void clear() {
//        this.head=null;

        while (head.next!=null){
            Node cur=head;
            while (cur!=null){
                Node curNext=cur.next;
                cur.next=null;
                cur=curNext;
            }
            head=null;
        }

    }

    /**
     *递归实现单列表的逆序打印
//     * @param head
     */
 /*   public void printList(Node head){
        if (head==null){
            return;
        }
        if(head.next==null){
            System.out.println(head.val);
        }
        printList(head.next);
        System.out.println(head.val);

    }*/
    public void printList3() {
        Stack<Node> stack=new Stack<>();
        Node cur=head;
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (!stack.empty()){
           Node top=stack.pop();
            System.out.println(top.val);
        }
    }
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch=s.charAt(i);
            if (ch=='{'||ch=='['||ch=='('){
               stack.push(ch);
            }else {
                //说明ch里面是右括号
                if (stack.empty()){
                    //右括号多
                    return false;
                }
                char top=stack.peek();
                if (top=='('&&ch==')'||top=='['&&ch==']'||top=='{'&&ch=='}'){
                    stack.pop();
                }else {
                    //左右括号不匹配
                    return false;
                }
            }

        }
        if (stack.empty()){
            return true;
        }else {
            return false;
        }

    }
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            if (!isOperation(tokens[i])){
                int a=Integer.parseInt(tokens[i]);
                stack.push(a);
            }else {
                int num1=stack.pop();
                int num2=stack.pop();
                switch (tokens[i]){
                    case "+":
                        stack.push(num2+num1);
                        break;
                    case "-":
                        stack.push(num2-num1);
                        break;
                    case "*":
                        stack.push(num2*num1);
                        break;
                    case "/":
                        stack.push(num2/num1);
                        break;
                }
            }
        }
return stack.pop();
    }
private  boolean isOperation(String opera){
        if(opera.equals("+")||opera.equals("-")||opera.equals("*")||opera.equals("/")){
            return true;
        }else {
            return false;
        }
}
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        if(pushV.length==0||popV.length==0){return false;}
        Stack<Integer> stack = new Stack<>();
        int j=0;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (j<popV.length&&!stack.empty()&&stack.peek().equals(popV[j])){
                stack.pop();
                j++;
            }
        }
        if (stack.empty()){
            return  true;
        }else {
            return false;
        }

    }

}
